// https://leetcode.cn/problems/maximal-rectangle/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
		int row = matrix.size();
		int col = matrix[0].size();
		
		vector<vector<int>> dp(row, vector<int>(col + 2));
		
		for(int i = 0; i < col; i++){
			dp[0][i+1] = matrix[0][i] == '1' ? 1 : 0;
		}
		dp[0][0] = 0;
		dp[0][col + 1] = 0;
		for(int i = 1; i < row; i++){
			for(int j = 0; j < col; j++){
				if(matrix[i][j] == '1'){
					dp[i][j+1] = dp[i-1][j+1] + 1;
				} else {
					dp[i][j+1] = 0;
				}
			}
			dp[i][0] = 0;
			dp[i][col + 1] = 0;
		}
		
		// for(int i = 0; i < row; i++){
			// for(int j = 0; j <= col+1; j++){
				// cout << dp[i][j] << ",";
			// }
			// cout << endl;
		// }
		// 下面需要用到单调栈
		int maxS = 0;
		
		for(int i = 0; i < row; i++){
			vector<int> st;
			st.push_back(0);
			for(int j = 1; j <= col + 1; j++){
				if(dp[i][st.back()] > dp[i][j]){
					while(dp[i][j] < dp[i][st.back()]){
						int back = st.back();
						st.pop_back();
						maxS = max((j - st.back() - 1) * dp[i][back], maxS);
					}
				}
				st.push_back(j);
			}
			st.clear();
		}
		return maxS;
    }
	
};

/*
		y{][}
		{1,0,1,1,1,1,0},
		{2,0,2,2,2,2,0},
		{3,1,3,3,3,3,1},
		{4,0,0,4,0,4,0}

*/

int main(){
	vector<vector<char>> matrix = {
		{'1','0','1','0','0'},
		{'1','0','1','1','1'},
		{'1','1','1','1','1'},
		{'1','0','0','1','0'}
		};
	Solution so;
	int s = so.maximalRectangle(matrix);
	cout << "max:" << s << endl;
	return 0;
}